package com.gofaraway.service.student.左神算法课.v2;

import com.gofaraway.service.student.leetcode.Demo10.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 二叉树相关算法 其中包括部分环形链表题目
 *
 * @author ChenPeng
 * @date 2025/5/10 17:12
 */
public class Code04_ErChaTree {

    /**
     * 先序遍历
     */
    public void pre(Node node) {
        if (node == null) {
            return;
        }
        System.out.println(node.val);
        pre(node.left);
        pre(node.right);
    }

    /**
     * 中序遍历
     */
    public void in(Node node) {
        if (node == null) {
            return;
        }
        in(node.left);
        System.out.println(node.val);
        in(node.right);
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        in2(root, list);
        return list;
    }

    public void in2(TreeNode node,List<Integer> list) {
        if (node == null) {
            return;
        }
        in2(node.left, list);
        list.add(node.val);
        in2(node.right, list);
    }

    /**
     * 后续遍历
     */
    public void pos(Node node) {
        if (node == null) {
            return;
        }

        pos(node.left);
        pos(node.right);
        System.out.println(node.val);
    }

    /****************下面是链表相关题***************/

    /**
     * 环形链表|
     * <p>
     * 快慢指针
     */
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode fast = head.next;
        ListNode slow = head;

        while (fast != slow) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }


    /**
     * 环形链表 2
     * <p>
     * leetcode链接：https://leetcode.cn/problems/linked-list-cycle-ii/?envType=study-plan-v2&envId=top-100-liked
     * 解法说明：先判断是否成环（快慢指针），成环再找第一个入环节点
     * 找 入环节点：成环后，快指针回到head节点，快指针步长也变为1，再次相交，那么这个相交节点就是第一个入环节点
     * 不要纠结找入环节点的方式怎么证明，记住就行
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        boolean hasCycle = false;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }
        if (!hasCycle) {
            return null;
        }

        //跳出循环 说明成环  开始找第一个入环节点
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }

        return fast;
    }


    /**
     * 二叉树的层序遍历(简单版 无法发现某一层的结束)
     * 利用队列先进先出的特性 实现
     */
    public static void level(Node node) {

        if (node == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);

        //循环终止条件 队列为空
        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            System.out.println(curr.val);
            //先左后右 curr的左右子节点依次入队列
            if (curr.left != null) {
                queue.add(curr.left);
            }
            if (curr.right != null) {
                queue.add(curr.right);
            }
        }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();

        if (root == null) {
            return ans;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<Integer> currLevel = new ArrayList<>();

        TreeNode currEnd = root;
        TreeNode nextEnd = null;

        while (!queue.isEmpty()) {
            TreeNode curr = queue.poll();

            currLevel.add(curr.val);
            if (curr.left != null) {
                queue.add(curr.left);
                nextEnd = curr.left;
            }
            if (curr.right != null) {
                queue.add(curr.right);
                nextEnd = curr.left;
            }
            //当前节点是本层的最后一个节点 那么重置 currLevel 并且 更新 currEnd
            if (curr == currEnd) {
                ans.add(currLevel);
                currLevel = new ArrayList<>();
                currEnd = nextEnd;
            }
        }

        return ans;
    }

    public static void levelV2(Node node) {

        if (node == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);

        Node currEnd = node;
        Node nextEnd = null;

        //循环终止条件 队列为空
        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            ArrayList<Object> list = new ArrayList<>();
            if (curr == currEnd) {

            }
            System.out.println(curr.val);
            //先左后右 curr的左右子节点依次入队列
            if (curr.left != null) {
                queue.add(curr.left);
            }
            if (curr.right != null) {
                queue.add(curr.right);
            }
        }
    }
}




class Node {

    int val;
    Node left;
    Node right;

    public Node(int val, Node left, Node right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


class ListNode {

    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }

}
